package com.leetcode.p100;

import com.bean.ListNode;
import com.utils.DataUtils;

public class Test143 {

    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode l2 = slow.next;
        slow.next = null;

        l2 = reserve(l2);

        merge(head, l2);
    }

    private ListNode reserve(ListNode listNode) {
        ListNode pre = null;
        ListNode cur = listNode;
        ListNode next = null;

        while (cur != null) {
            next = cur.next;

            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private void merge(ListNode l1, ListNode l2) {
        ListNode l1_temp;
        ListNode l2_temp;

        while (l1 != null && l2 != null) {
            l1_temp = l1.next;
            l2_temp = l2.next;

            l1.next = l2;
            l2.next = l1_temp;

            l1 = l1_temp;
            l2 = l2_temp;
        }
    }

    public static void main(String[] args) {
        ListNode listNode = DataUtils.getOneToNumberListNode(13);

        Test143 test = new Test143();
        test.reorderList(listNode);
        DataUtils.printListNode(listNode);
    }

}
